package com.hanxiaozhang.link.fastslowpointer;

import java.util.ArrayList;

/**
 * 〈一句话功能简述〉<br>
 * 〈快慢指针问题〉
 *
 * @author hanxinghua
 * @create 2021/10/24
 * @since 1.0.0
 */
public class FastSlowPointerNode {


    public static void main(String[] args) {

        // 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7   偶数 上中点3 下中点4
        // 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8  奇数  中点4
        Node test = null;
        test = new Node(0);
        test.next = new Node(1);
        test.next.next = new Node(2);
        test.next.next.next = new Node(3);
        test.next.next.next.next = new Node(4);
        test.next.next.next.next.next = new Node(5);
        test.next.next.next.next.next.next = new Node(6);
        test.next.next.next.next.next.next.next = new Node(7);
        // test.next.next.next.next.next.next.next.next = new Node(8);

        Node ans1 = null;
        Node ans2 = null;

        System.out.println("----midOrUpMidNode----");
        ans1 = midOrUpMidNode(test);
        ans2 = right1(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

        System.out.println("----midOrDownMidNode----");
        ans1 = midOrDownMidNode(test);
        ans2 = right2(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

        System.out.println("----midOrUpMidPreNode----");
        ans1 = midOrUpMidPreNode(test);
        ans2 = right3(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

        System.out.println("----midOrDownMidPreNode----");
        ans1 = midOrDownMidPreNode(test);
        ans2 = right4(test);
        System.out.println(ans1 != null ? ans1.value : "无");
        System.out.println(ans2 != null ? ans2.value : "无");

    }


    /**
     * 快慢指针问题
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点
     * <p> slow指针起点： head.next
     * <p> fast指针起点： head.next.next
     *
     * @param head
     * @return
     */
    public static Node midOrUpMidNode(Node head) {
        // head == null 返回 head 即 null
        // head != null 和 head.next == null 长度1个（奇数）  返回 head
        // head != null 和 head.next != null 长度2个（偶数） 返回 head
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        // ---- 潜台词：链表有3个点以上
        // 慢指针 头结点下一个
        Node slow = head.next;
        // 快指针 头结点下两个
        Node fast = head.next.next;
        /*
        变种：
        // 慢指针
        Node slow = head;
        // 快指针
        Node fast = head;
        这种情况，在一次循环后，等于以上初始值
         */
        // 快指针的下一个不为空 并且 快指针的下两个不为空
        while (fast.next != null && fast.next.next != null) {
            // 慢指针 = 慢指针的下一个
            slow = slow.next;
            // 快指针 = 快指针的下两个
            fast = fast.next.next;
        }
        return slow;
    }


    /**
     * 快慢指针问题
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     * <p> slow指针起点： head.next
     * <p> fast指针起点： head.next
     *
     * @param head
     * @return
     */
    public static Node midOrDownMidNode(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        Node slow = head.next;
        Node fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
     * <p> slow指针起点： head
     * <p> fast指针起点： head.next.next
     *
     * @param head
     * @return
     */
    public static Node midOrUpMidPreNode(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node slow = head;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    /**
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
     * <p> slow指针起点： head
     * <p> fast指针起点： head.next
     *
     * @param head
     * @return
     */
    public static Node midOrDownMidPreNode(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        if (head.next.next == null) {
            return head;
        }
        Node slow = head;
        Node fast = head.next;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    /**
     * 对数器
     * 输入链表头节点，奇数长度返回中点，偶数长度返回上中点。
     * <p>
     * 把节点放入数组中，找出(arr.size() - 1) / 2
     *
     * @param head
     * @return
     */
    public static Node right1(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 1) / 2);
    }

    /**
     * 对数器
     * 输入链表头节点，奇数长度返回中点，偶数长度返回下中点
     * <p>
     * 把节点放入数组中，找出arr.size() / 2
     *
     * @param head
     * @return
     */
    public static Node right2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get(arr.size() / 2);
    }

    /**
     * 对数器
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
     * <p>
     * 把节点放入数组中，找出(arr.size() - 3) / 2
     *
     * @param head
     * @return
     */
    public static Node right3(Node head) {
        if (head == null || head.next == null || head.next.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 3) / 2);
    }

    /**
     * 对数器
     * 输入链表头节点，奇数长度返回中点前一个，偶数长度返回下中点前一个
     * <p>
     * 把节点放入数组中，找出(arr.size() - 2) / 2
     *
     * @param head
     * @return
     */
    public static Node right4(Node head) {
        if (head == null || head.next == null) {
            return null;
        }
        Node cur = head;
        ArrayList<Node> arr = new ArrayList<>();
        while (cur != null) {
            arr.add(cur);
            cur = cur.next;
        }
        return arr.get((arr.size() - 2) / 2);
    }


    public static class Node {
        public int value;
        public Node next;

        public Node(int v) {
            value = v;
        }
    }

}
